package dst.search_tree.avl;

import java.util.ArrayList;

/**
 *
 * @author Shimu
 * @date 20-Jul-2012
 */
public abstract class BinarySearchTree <T extends Comparable<T>> {
    
    /**
     * The number of nodes in the BinarySearchTree
     */
    protected int size;
        
    /**
     * Initialize a BinarySearchTree with the root containing the given data
     * 
     * @param rootData 
     */
    public BinarySearchTree() {
        this.size = 0;
    }
    
    /**
     * An inner class that represents the tree nodes in the binary search tree
     */
    protected class TreeNode {
        
        /** The data stored in this TreeNode */
        private T data;

        /** The left child of this TreeNode */
        private TreeNode left;
        
        /** The right child of this TreeNode */
        private TreeNode right;
        
        protected TreeNode(T data) {
            this.left = getSentinel();
            this.right = getSentinel();
            this.data = data;
        }
        
        protected T getData() {
            return data;
        }
        
        protected TreeNode left() {
            return left;
        }
        
        protected TreeNode right() {
            return right;
        }
        
        protected void setLeft(TreeNode newLeft) {
            this.left = newLeft;
        }
        
        protected void setRight(TreeNode newRight) {
            this.right = newRight;
        }
        
        /**
         * Returns true if the data stored in this node is strictly less than
         * the given data.
         * 
         * @param otherData
         * @return 
         */
        protected boolean lessThan(T otherData) {
            return this.data.compareTo(otherData) < 0;
        }
        
        /**
         * Returns true if the data stored in this node is strictly less than
         * the data stored in the given node.
         * 
         * @param otherData
         * @return 
         */
        protected boolean lessThan(TreeNode other) {
            return this.lessThan(other.data);
        }
        
        /**
         * Returns true if the data stored in this node is strictly greater than
         * the given data.
         * 
         * @param otherData
         * @return 
         */
        protected boolean greaterThan(T otherData) {
            return this.data.compareTo(otherData) > 0;
        }
        
        /**
         * Returns true if the data stored in this node is strictly greater than
         * the data stored in the given node.
         * 
         * @param otherData
         * @return 
         */
        protected boolean greaterThan(TreeNode other) {
            return this.greaterThan(other.data);
        }
        
        /**
         * Returns true if the data stored in this node is equal to
         * the given data.
         * 
         * @param otherData
         * @return 
         */
        protected boolean equal(T otherData) {
            return this.data.compareTo(otherData) == 0;
        }
        
        /**
         * Returns true if the data stored in this node is equal to
         * the data stored in the given node.
         * 
         * @param other
         * @return 
         */
        protected boolean equal(TreeNode other) {
            return this.equal(other.data);
        }
        
        /**
         * Returns true if this node has a left child.
         * 
         * @return 
         */
        protected boolean hasLeftChild(){
            return left.exists();
        }
        
        /**
         * Returns true if this node has a right child.
         * 
         * @return 
         */
        protected boolean hasRightChild(){
            return right.exists();
        }
        
        /**
         * Returns true if this node exists, i.e. this != getSentinel().
         * @return 
         */
        protected boolean exists() {
            return this != getSentinel();
        }
        
        /**
         * Return the AvlNode containing the given data. Returns SENTINEL
         * if no AvlNode in the tree contains the given data.
         * 
         * @param data
         * @return 
         */
        protected boolean search(T data) {
            TreeNode current = this;
            while (current.exists() && !current.equal(data)) {
                if (current.greaterThan(data)) {
                    current = current.left;
                
                } else { // this.data < data
                    current = current.right;
                }
            }
            return current.exists();
        }
        
        /**
         * Rotate the tree rooted at this node to the left.
         * 
         */
        protected void rotateLeft(TreeNode parent) {
            // There is no checking for SENTINEL since you'll never call
            // a left rotation if the right child is SENTINEL

            /*
             * Case 1: Node A is the left child of parent
             * 
             * Before:
             *          P (parent)
             *       /     \
             *      /       \ 
             *     /         \
             *    /\          A (this)
             *   /T0\       /    \
             *  ------     /      \
             *            /         B (this.right)
             *           /\       /   \ 
             *          /T1\     /     \
             *         ------   /\     /\
             *                 /T2\   /T3\
             *                ------ ------
             * 
             * After:
             *          P (parent)
             *       /     \
             *      /       \ 
             *     /         \
             *    /\          B (this.right)
             *   /T0\       /    \
             *  ------     /      \
             *            /        \
             *           A (this)  /\
             *         /   \      /T3\
             *        /     \    ------
             *       /\     /\  
             *      /T1\   /T2\
             *     ------ ------
             * 
             * Case 2: Node A is the right child of parent
             * 
             * Before:
             *             P (parent)
             *           /   \
             *          /     \
             *         /       \
             * (this) A        /\
             *      /    \    /T0\ 
             *     /      \  ------
             *    /         B (this.right)
             *   /\       /   \ 
             *  /T1\     /     \
             * ------   /\     /\
             *         /T2\   /T3\
             *        ------ ------
             * 
             * After:
             *                    P (parent)
             *                 /     \
             *                /       \ 
             *               /        /\ 
             * (this.right) B        /T0\
             *           /     \    ------
             *          /       \
             *         /         \
             *        A (this)   /\
             *      /   \       /T3\
             *     /     \     ------
             *    /\     /\  
             *   /T1\   /T2\
             *  ------ ------
             */
            TreeNode A, B;


            A = this;
            B = this.right();

            if (parent.exists()) {
                if (parent.right() == A) {
                    // case 1
                    parent.setRight(B);
                } else {
                    // case 2
                    parent.setLeft(B);
                }
            }

            A.setRight(B.left());
            B.setLeft(A);
        }
        
        /**
         * Performs in-order traversal on the tree rooted at this node.
         * This will append in-order the nodes of the tree.
         * 
         * @param orderedList 
         */
        protected void inOrderTraversal(ArrayList<T> orderedList) {
            if (this.hasLeftChild()) {
                this.left().inOrderTraversal(orderedList);
            }

            orderedList.add(this.getData());

            if (this.hasRightChild()) {
                this.right().inOrderTraversal(orderedList);
            }
        }
    }
    
    /**
     * Returns the number of nodes in this tree.
     * 
     * @return 
     */
    public int getSize() {
        return size;
    }
    
    /**
     * Returns true if the given data is contained in this AvlTree,
     * false otherwise.
     * 
     * @param data
     * @return 
     */
    public boolean search(T data) {
        return getRoot().search(data);
    }
    
    /**
     * Performs in-order traversal on the AvlTree. This will append 
     * in-order the data of the tree to an ArrayList and return the ArrayList.
     * 
     * @return an ArrayList containing the nodes of the tree in-order.
     */
    public ArrayList<T> inOrderTraversal() {
        ArrayList<T> orderedList = new ArrayList<T>();
        getRoot().inOrderTraversal(orderedList);
        return orderedList;
    }
    
    /**
     * Prints the nodes of this AvlTree in-order.
     */
    public void printInOrder() {
        ArrayList<T> list = inOrderTraversal();
        for (T element : list) {
            System.out.println(element);
        }
    }
    
    /**
     * Adds the given data to this BinarySearchTree.
     * 
     * @param data
     */
    public abstract void add(T data);
    
    /**
     * Returns a sentinel TreeNode that servers as null, NIL, or the children 
     * of a leaf node
     */
    protected abstract TreeNode getSentinel();
    
    /**
     * Returns the root of this BinarySearchTree
     * @return 
     */
    protected abstract TreeNode getRoot();
       
}
